// 06-图3 六度空间
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*============== 队列 ===================*/
// 队列元素类型
#ifndef QueueElementType
#define QueueElementType int
#endif

typedef struct LinkedNode LinkedNode;
struct LinkedNode {
    QueueElementType data;
    LinkedNode* next;
};

typedef struct Queue Queue;
struct Queue {
    // 队列的头尾节点
    LinkedNode* head;
    LinkedNode* tail;
};

Queue* createQueue() {
    Queue* queue = (Queue*) malloc(sizeof(Queue));
    queue->head = queue->tail = NULL;
    return queue;
}

int isEmptyQueue(Queue *queue) {
    return queue->head == NULL;
}

void enQueue(Queue *queue, QueueElementType data) {
    LinkedNode* node = (LinkedNode*)malloc(sizeof(LinkedNode));
    node->data = data;
    node->next = NULL;
    if (queue->head == NULL) {
        queue->head = queue->tail = node;
        return;
    }
    queue->tail->next = node;
    queue->tail = node;
}

QueueElementType deQueue(Queue* queue) {
    // 取数据
    QueueElementType data = queue->head->data;
    // 移动头指针
    LinkedNode* node = queue->head;
    queue->head = node->next;
    // 释放内存
    free(node);
    
    return data;
}

/*============== 图 ===================*/
// 定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    for (int v=0; v < g->vertexNum; v++) {
        free(g->g[v]);
    }
    free(g->g);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
}

// 从标准输入读取边信息，顶点下标从0开始
void readEdgeV0(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        insertEdge(g, v1, v2, 1);
    }
}

void readEdgeV0WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, v1, v2, dist);
    }
}

// 从标准输入读取边信息，顶点下标从1开始编号
void readEdgeV1(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        insertEdge(g, --v1, --v2, 1);
    }
}

void readEdgeV1WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, --v1, --v2, dist);
    }
}

void print1D(char* name, int array[], int n) {
    printf("%s: ", name);
    for (int i=0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}

/*=============================*/
int bfs(MGraph* g, int v, int* visited) {
    int level = 0; // 访问的层数
    int last = v;  // 当前层的最后一个节点，第一次调用时，即当前节点v
    int tail; // 下一层的最后一个节点 
    int count = 1; // 6层内与当前节点有关联的节点数，即认识的人数
    visited[v] = 1;
    Queue* queue = createQueue();
    enQueue(queue, v);
    while (!isEmptyQueue(queue)) {
        int v = deQueue(queue);
        for (int i=0; i<g->vertexNum; i++) {
            if (g->g[v][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enQueue(queue, i);
                count++;
                tail = i;
            }
        }
        if (v == last) {
            // 弹出的节点是当前层的最后一个节点
            level++; // 层数加1
            last = tail; // 当前层的最后一个节点更新为下层的最后一个节点
        }
        if (level == 6) {
            break;
        }
    }
    return count;
}

int sds(MGraph* g) {
    int* visited = (int*)calloc(g->vertexNum, sizeof(int));
    for (int i=0; i<g->vertexNum; i++) {
        memset(visited, 0, sizeof(int)*g->vertexNum);
        int count = bfs(g, i, visited);
        printf("%d: %.2f%%\n", i+1, 100.0*count/g->vertexNum);
    }
    free(visited);
}

int main() {
    int vn, en;
    scanf("%d %d", &vn, &en);
    MGraph* graph = createGraph(UndirectedGraph, 0, vn);
    readEdgeV1(graph, en);
    // printGraph(graph);
    sds(graph);
    freeGraph(graph);
    return 0;
}

